package simple;

import data.TreeNode;
import javafx.util.Pair;

import java.util.Stack;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/5/31 14:33
 */
public class No110_平衡二叉树 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        Solution110 solution110 = new Solution110();
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);

        root.right.left = new TreeNode(15);
        root.right.right= new TreeNode(7);

        boolean balanced = solution110.isBalanced(root);
        System.out.println(balanced);

    }
}

class Solution110 {
    public boolean isBalanced(TreeNode root) {
        boolean flag = true;
        if (root == null) {
            return true;
        } else {
            int leftDeep = getDeep(root.left);
            int rightDeep = getDeep(root.right);
            flag = Math.abs(leftDeep - rightDeep) <= 1;
        }
        return flag && isBalanced(root.left) && isBalanced(root.right);
    }

    //获取root树深度
    public int getDeep(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //(树,深度)
        Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
        stack.push(new Pair<>(root, 1));
        int deep = 1;
        int maxDeep = deep;
        while (!stack.isEmpty()) {
            Pair<TreeNode, Integer> checkTree = stack.pop();
            //获取当前节点深度
            deep = checkTree.getValue();
            if (checkTree.getKey().left == null && checkTree.getKey().right == null) {
                continue;
            }
            //一定有子树,deep+1
            deep++;
            maxDeep = Math.max(deep, maxDeep);
            if (checkTree.getKey().left == null) {
                //右边有子树
                stack.push(new Pair<>(checkTree.getKey().right, deep));
            } else if (checkTree.getKey().right == null) {
                //左边有子树
                stack.push(new Pair<>(checkTree.getKey().left, deep));
            } else {
                stack.push(new Pair<>(checkTree.getKey().right, deep));
                stack.push(new Pair<>(checkTree.getKey().left, deep));
            }
        }
        return maxDeep;
    }

}



    //public boolean isBalanced(TreeNode root) {
    //    boolean flag = true;
    //    if (root == null) {
    //        return true;
    //    } else {
    //        int leftDeep = getDeep(root.left);
    //        int rightDeep = getDeep(root.right);
    //        flag = Math.abs(leftDeep - rightDeep) <= 1;
    //    }
    //    return flag && isBalanced(root.left) && isBalanced(root.right);
    //}
    //
    ////获取root树深度
    //public int getDeep(TreeNode root) {
    //    int deep = -34957349;
    //    if (root == null) {
    //        deep = 0;
    //        return deep;
    //    } else {
    //        deep = 1;
    //        deep += Math.max(getDeep(root.left), getDeep(root.right));
    //    }
    //    return deep;
    //}